package LimitedTimeGame.Day_0215;

/**
 * @author zxc
 * @date 2023/02/15 10:31
 **/

/**
 * 题目 ：检查[好数组]
 * 题目详述 ：
 * 给你一个正整数数组 nums，你需要从中任选一些子集，然后将子集中每一个数乘以一个 任意整数，并求出他们的和。
 * 假如该和结果为1，那么原数组就是一个「好数组」，则返回 True；否则请返回 False。
 *
 * 提示：
 * 1 <= nums.length <= 10^5
 * 1 <= nums[i] <= 10^9
 *
 */
public class IsGoodArray {
    /**
     * 思路 ：
     * [裴属定理]
     * （1）对于不全为零的任意整数 a 和 b，记 g = gcd(a,b)，其中gcd(a,b) 为 a 和 b 的最小公约数;
     *  则对于任意整数 x 和 y ,都满足 a*x + b*y 是 g 的倍数，
     *  特别地，存在整数 x 和 y 满足 a*x + b*y = g。
     * （2）可以将其推广到多个整数
     *  ===>
     *  即对于不全为0的多个任意整数，其中设k为这多个任意整数的最大公约数;
     *  则，对于任意整数 x1,x2,...,xn,都满足 a*x1 + b*x2 + ... + n*xn 为 k的倍数
     *  特殊情况 ：a*x1 + b*x2 + ... + n*xn = k;
     *  <===> 即，题目转换为求解对应子数组的最大公约数;
     * （3）即，若是该nums数组中存在若干个互质整数（即，整数之间的最大公约数为1）的话，
     *  ===>代表了所选取的子数组集合中所有元素的最大公约数为1;
     * （4）即，整个nums数组由于若干个互质整数的存在，所以整个nums数组中所有元素的最大公约数为1;
     * <===>
     * 即，题目又转化为求解整个nums数组所有元素的最大公约数;
     *
     * 补充 ：
     * 求取多个元素的最大公约数的方法 --- 辗转相除法;
     * 假设f(x,y)是元素x，y的最大公约数;
     * （1）即，while循环执行 f(x,y) ===> f(y , x % y)操作，直至 x % y == 0，则 y 就是x，y之间的最大公约数;
     *  ===> 若是x > y的话，上述操作会将x,y位置进行互换;
     *
     * @param nums
     * @return
     */
    public boolean isGoodArray(int[] nums) {
        int maxDivisor = nums[0];
        int len = nums.length;
        // 遍历整个nums数组，求解nums数组中所有元素之间的最大公约数
        // 若是最大公约数为1的话，即代表了nums数组中存在若干个互质整数; ===> 即，原数组为[好数组];
        for(int i = 0 ; i < len ; i++){
            maxDivisor = gcd(maxDivisor , nums[i]);
            if(maxDivisor == 1){
                return true;
            }
        }
        return false;
    }
    // 辗转相除法 ：求解两个数之间的最大公约数
    public int gcd(int num1 , int num2){
        while(num2 != 0){
            int temp = num1;
            num1 = num2;
            num2 = temp % num2;
        }
        return num1;
    }
}
